package com.leetcode.KMP;


import java.util.Arrays;

public class KMPTest {
    public static void main(String[] args) {
        String haystack = "aaaabbbaaaabc";
        String needle =   "aaaabc";
        int index = strStr(haystack, needle);
        System.out.println("index = " + index);
    }

    static int strStr(String haystack, String needle) {
        //特殊情况判断
        if (haystack == null || needle == null) {
            return -1;
        }
        if (needle.length() == 0) {
            return 0;
        }
        if (haystack.length() < needle.length()) {
            return -1;
        }
        /**
         * 每次匹配，若不相等，j的值需要更新：j = next[j],i不变，因为i需要再次进行判断
         * 仅当j == -1时，说明第一个字符就不相等，则i++，j = 0
         */
        int[] next = getNext(needle);
        System.out.println(Arrays.toString(needle.toCharArray()));
        System.out.println(Arrays.toString(next));

        int j = 0;//控制指向needle的索引
        int index = -1;//用于保存匹配成功时的开始下标
        for (int i = 0; i < haystack.length(); i++) {
            /*
            当j == -1时，更新:j = 0(此时j++刚好等于0)，i ++
            当haystack.charAt(i) == needle.charAt(j)时，更新：j++，i++
            因此两种情况都做同样的事情，可以放在一个if中
            * */
            if (j == -1 || haystack.charAt(i) == needle.charAt(j)) {
                j++;

                //如果条件满足，说明needle已经全部匹配成功了，跳出循环，返回index的值
                if (j == next.length) {
                    index = i - j + 1;
                    break;
                }

                continue;//这里continue，以下的语句不会执行，根据for循环，i会++
            }

            //到达此处说明，haystack.charAt(i) != needle.charAt(j)
            //则j更新，i不变，因为i需要再次进行判断
            j = next[j];
            i--;//for循环的结尾，i会++，这里i--就相当于i不变
        }
        return index;
    }

    /**
     * next[i]:0~i(不包含i)的字串中，公共前后缀的长度。
     * 前缀：不包含最后一个字符
     * 后缀：不包含第一个字符
     * 两个特殊值：
     * next[0] = -1;第一个值，比较特殊
     * next[1] = 0;根据前后缀的定义，next[1]不包含前后缀，定义为0
     * 如字符串"aaaabc"的next数组为
     * str: [a, a, a, a, b, c]
     * next:[-1, 0, 1, 2, 3, 0]
     * 为什么这里next[3] = 2，可以看到str[0~2]是三个字符'a'，next[3]保存3不是更好吗？
     * 答：next数组的定义并不是唯一的，因此next[i]的值的含义也有所不同，这里的定义可以结合ppt和代码，会发现处理索引会更加方便，
     * 不用出现多余的索引转换（比如长度为9，对应的索引应该是8，因为索引是从0开始的）
     *
     */
    static int[] getNext(String t) {
        if (t == null) {
            return null;
        }
        if (t.length() == 0) {
            return new int[0];
        }

        int[] next = new int[t.length()];
        next[0] = -1;

        if (t.length() == 1) {
            return next;
        }
        next[1] = 0;
        // ↑ 以上，初始化结束。

        //j 的定义是：保存next[i - 1]的值，这里初始化为0即保存next[1]的值，因为i从2开始循环
        int j = 0;
        for (int i = 2; i < next.length; i++) {
            //以下为算法核心，详情见KMP.pptx
            while (j > 0 && t.charAt(i - 1) != t.charAt(j)) {
                j = next[j];
            }
            if (t.charAt(i - 1) == t.charAt(j)) {
                j++;
            }
            next[i] = j;
        }
        return next;
    }
}
